#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef struct Qnode
{
    int data;
    struct Qnode* next;
}Qnode;

typedef struct Queue{
    Qnode* head;
    Qnode* tail;
    int size;
}Queue;

void QueueInit(Queue* pq)
{
    assert(pq);

    pq->head=pq->tail=NULL;
    pq->size=0;
}

void QueueDestory(Queue* pq)
{
    assert(pq);
    
    Qnode* cur=pq->head;
    while(cur)
    {
        Qnode* next=cur->next;
        free(cur);
        cur=next;
    }

    pq->size=0;
    pq->head=pq->tail=NULL;
}

void QueuePush(Queue* pq,int x)
{
    assert(pq);

    Qnode* newnode=(Qnode*)malloc(sizeof(Qnode));
    if(newnode==NULL)
    {
        perror("newnode malloc");
        return ;
    }
    newnode->data=x;
    newnode->next=NULL;
    //插入节点】
   if (pq->head == NULL)
	{
		assert(pq->tail == NULL);

		pq->head = pq->tail = newnode;
	}
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }
    pq->size++;
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head&&pq->tail);
    //删除节点
    if(pq->head==pq->tail)
    {
        free(pq->head);
        pq->head=pq->tail=NULL;
        pq->size--;
        return ;
    }
    else
    {
        Qnode* next=pq->head->next;
        free(pq->head);
        pq->head=next;
    }
    pq->size--;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}

bool QueueIsEmepty(Queue*pq)
{
    assert(pq);

    if(pq->head==NULL&&pq->tail==NULL)
    {
        return true;
    }
    return false;
}

int QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head&&pq->tail);

    return pq->head->data;
}

int QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head&&pq->tail);

    return pq->tail->data;
}

typedef struct {
   Queue Q1;
   Queue Q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* stq=(MyStack*)malloc(sizeof(MyStack));
    if(stq==NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    QueueInit(&stq->Q1);
    QueueInit(&stq->Q2);
    return stq;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueIsEmepty(&obj->Q1))
    {
        QueuePush(&obj->Q1, x);
    }
    else
    {
        QueuePush(&obj->Q2, x);

    }
}

int myStackPop(MyStack* obj) {
    Queue* empty=&obj->Q1;
    Queue* nonempty=&obj->Q2;
    if(QueueIsEmepty(&obj->Q2))
    {
        empty=&obj->Q2;
        nonempty=&obj->Q1;
    }

    //倒数据
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    
    int temp=QueueFront(nonempty);
    QueuePop(nonempty);
    return temp;
}

int myStackTop(MyStack* obj) {
    if(!QueueIsEmepty(&obj->Q1))
    {
        return QueueBack(&obj->Q1);
    }
    else
    {
        return QueueBack(&obj->Q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    if(QueueIsEmepty(&obj->Q1)&&QueueIsEmepty(&obj->Q2))
    {
        return true;
    }
    else
    {
        return false;
    }
}

void myStackFree(MyStack* obj) {
    QueueDestory(&obj->Q1);
    QueueDestory(&obj->Q2);
    free(obj);
}


//int main()
//{
//	MyStack* stq=myStackCreate() ;
//	myStackPush(stq,1);
//	myStackPush(stq,2);
//	myStackPush(stq,3);	
//	myStackPush(stq,4);
//	
//	myStackPop(stq);
//	myStackPop(stq);
//	myStackPop(stq);
//	
//	return 0;
//
//}
